package io.github.hadyang.leetcode.random;

import java.util.LinkedList;
import java.util.List;

import io.github.hadyang.leetcode.TreeNode;

/**
 * 给定一个二叉树，返回它的 前序 遍历。
 *
 * <p> 示例:
 *
 * <p>输入: [1,null,2,3] 1 \ 2 / 3
 *
 * <p>输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q144 {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    List<Integer> res = new LinkedList<>();

    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      if (node == null) continue;
      stack.push(node.right);
      stack.push(node.left);

      res.add(node.val);
    }
    return res;
  }
}
